//
// Created by ASUS on 2024/2/29.
//
/*
给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边 。
给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。
返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。
示例 1:
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
示例 2:
输入: n = 1, edges = []
输出: [0]
示例 3:
输入: n = 2, edges = [[1,0]]
输出: [1,1]
提示:
1 <= n <= 3 * 10^4
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
给定的输入保证为有效的树
 */
#include <bits/stdc++.h>
using namespace std;

vector<int> sumOfDistancesInTree(int n, vector<vector<int>> &edges) {
	vector<vector<int>> g(n); // g[x] 表示 x 的所有邻居
	for (auto &e: edges) {
		int x = e[0], y = e[1];
		g[x].push_back(y);
		g[y].push_back(x);
	}

	vector<int> ans(n);
	vector<int> size(n, 1); // 注意这里初始化成 1 了，下面只需要累加儿子的子树大小
	function<void(int, int, int)> dfs = [&](int x, int fa, int depth) {
		ans[0] += depth; // depth 为 0 到 x 的距离
		for (int y: g[x]) { // 遍历 x 的邻居 y
			if (y != fa) { // 避免访问父节点
				dfs(y, x, depth + 1); // x 是 y 的父节点
				size[x] += size[y]; // 累加 x 的儿子 y 的子树大小
			}
		}
	};
	dfs(0, -1, 0); // 0 没有父节点

	function<void(int, int)> reroot = [&](int x, int fa) {
		for (int y: g[x]) { // 遍历 x 的邻居 y
			if (y != fa) { // 避免访问父节点
				ans[y] = ans[x] + n - 2 * size[y];
				reroot(y, x); // x 是 y 的父节点
			}
		}
	};
	reroot(0, -1); // 0 没有父节点
	return ans;
}
